<html>
<head>
  <title>01线性结构</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="660"/>
<h1>01线性结构</h1>

<div>
<span><div><div><span><font style="font-size: 24pt; color: rgb(106, 0, 129);"><span style="line-height: 30px;"><b>理论介绍</b></span></font></span></div><div><b><span style="font-size: 21px;"><span style="color: rgb(28, 51, 135);">线性表</span></span></b></div><div><span style="font-size: 16px;">多项式表示问题的启示：</span></div><div><span style="font-size: 16px;">1. 同一个问题可以有不同的表示（存储）方法</span></div><div><span style="font-size: 16px;">2. 有一类共性问题：有序线性序列的组织和管理</span></div><div><span style="font-size: 16px;">线性表（Linear List）：由同类型数据元素构成有序序列的线性结构</span></div><ul><li><span style="font-size: 16px;">表中元素个数称为线性表的长度</span></li><li><span style="font-size: 16px;">线性表没有元素时，称为空表</span></li><li><span style="font-size: 16px;">表起始位置成表头，表结束为止称表尾</span></li></ul><div><br/></div><div><span style="font-size: 21px;"><span style="color: rgb(28, 51, 135);"><b>链式表</b></span></span></div><div><span style="font-size: 16px;">     链式表存储多项式</span></div><div>          <img src="01线性结构_files/Image.png" type="image/png" data-filename="Image.png" style="height:auto;" width="540"/></div><div><span style="color: rgb(28, 51, 135);"><span style="font-size: 16px;">线性表的抽象数据类型描述</span></span></div><div><span style="font-size: 16px;">类型名称：线性表（List）</span></div><div><span style="font-size: 16px;">数据对象集：线性表是 n (≥0)个元素构成的有序序列( a1, a2, ¼,an )</span></div><div><span style="font-size: 16px;">操作集：线性表L 属于 List，整数i表示位置，元素X 属于 ElementType，</span></div><div><span style="font-size: 16px;"><b><span style="color: rgb(123, 0, 61);">线性表基本操作</span></b>主要有：</span></div><div><span style="font-size: 16px;">1、List MakeEmpty()：初始化一个空线性表L；</span></div><div><span style="font-size: 16px;">2、ElementType FindKth( int K, List L )：根据位序K，返回相应元素 ；</span></div><div><span style="font-size: 16px;">3、int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置；</span></div><div><span style="font-size: 16px;">4、void Insert( ElementType X, int i, List L)：在位序i前插入一个新元素X；</span></div><div><span style="font-size: 16px;">5、void Delete( int i, List L )：删除指定位序i的元素；</span></div><div><span style="font-size: 16px;">6、int Length( List L )：返回线性表L的长度n。</span></div><div><img src="01线性结构_files/Image [1].png" type="image/png" data-filename="Image.png" style="height:auto;" width="537"/></div><div><br/></div><div><span style="color: rgb(28, 51, 135);"><b><span style="font-size: 21px;">堆栈</span></b></span></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><span style="color: rgb(28, 51, 135);"><b><span style="font-size: 21px;">队列</span></b></span></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><font style="font-size: 24pt; color: rgb(106, 0, 129);"><b>题目及应用</b></font></div><div><br/></div><div><br/></div><div><br/></div><div><img src="01线性结构_files/Image [2].png" type="image/png" data-filename="Image.png"/></div><div><br/></div><div><br/></div><div><h1>Remove Duplicates from Sorted List</h1></div><div><h3>Problem Statement</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given a sorted linked list, delete all duplicates such that each element</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">appear only</span> <span style="-en-paragraph: true; font-style: italic;">once</span><span style="-en-paragraph: true;">.</span></div><h4>Example</h4><div>Given 1-&gt;1-&gt;2, return 1-&gt;2.</div><div><span style="-en-paragraph: true;">Given</span> <span style="-en-paragraph: true;">1-&gt;1-&gt;2-&gt;3-&gt;3</span><span style="-en-paragraph: true;">, return</span> <span style="-en-paragraph: true;">1-&gt;2-&gt;3</span><span style="-en-paragraph: true;">.</span></div></div><h2>题解</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">遍历之，遇到当前节点和下一节点的值相同时，删除下一节点，并将当前节点</span><span style="-en-paragraph: true;">next</span><span style="-en-paragraph: true;">值指向下一个节点的</span><span style="-en-paragraph: true;">next</span><span style="-en-paragraph: true;">, 当前节点首先保持不变，直到相邻节点的值不等时才移动到下一节点。</span></div><h3>Python</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>&quot;&quot;&quot;</div><div>Definition of ListNode</div><div>class ListNode(object):</div><div>    def __init__(self, val, next=None):</div><div>        self.val = val</div><div>        self.next = next</div><div>&quot;&quot;&quot;class Solution:</div><div>    &quot;&quot;&quot;</div><div>    @param head: A ListNode</div><div>    @return: A ListNode</div><div>    &quot;&quot;&quot;</div><div>    def deleteDuplicates(self, head):</div><div>        curt = head</div><div>        while curt:</div><div>            while curt.next and curt.next.val == curt.val:</div><div>                curt.next = curt.next.next</div><div>            curt = curt.next</div><div>        return head</div></div><div><h3>源码分析</h3><ol><li>首先进行异常处理，判断head是否为NULL</li><li>遍历链表，curr-&gt;val == curr-&gt;next-&gt;val时，保存curr-&gt;next，便于后面释放内存(非C/C++无需手动管理内存)</li><li>不相等时移动当前节点至下一节点，注意这个步骤必须包含在else中，否则逻辑较为复杂</li></ol><div><br/></div></div><h1>Remove Duplicates from Sorted List II</h1><div><h3>Problem Statement</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given a sorted linked list, delete all nodes that have duplicate numbers,</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">leaving only</span> <span style="-en-paragraph: true; font-style: italic;">distinct</span> <span style="-en-paragraph: true;">numbers from the original list.</span></div><h4>Example</h4><div>Given 1-&gt;2-&gt;3-&gt;3-&gt;4-&gt;4-&gt;5, return 1-&gt;2-&gt;5.</div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given</span> <span style="-en-paragraph: true;">1-&gt;1-&gt;1-&gt;2-&gt;3</span><span style="-en-paragraph: true;">, return</span> <span style="-en-paragraph: true;">2-&gt;3</span><span style="-en-paragraph: true;">.</span></div><h2>题解</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">上题为保留重复值节点的一个，这题删除全部重复节点，看似区别不大，但是考虑到链表头不确定(可能被删除，也可能保留)，因此若用传统方式需要较多的if条件语句。这里介绍一个</span><span style="-en-paragraph: true; font-weight: bold;">处理链表头节点不确定的方法——引入dummy node.</span></div><div>ListNode *dummy = new ListNode(0);</div><div>dummy-&gt;next = head;</div><div>ListNode *node = dummy;</div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">引入新的指针变量</span><span style="-en-paragraph: true;">dummy</span><span style="-en-paragraph: true;">，并将其next变量赋值为head，考虑到原来的链表头节点可能被删除，故应该从dummy处开始处理，这里复用了head变量。考虑链表</span><span style="-en-paragraph: true;">A-&gt;B-&gt;C</span><span style="-en-paragraph: true;">，删除B时，需要处理和考虑的是A和C，将A的next指向C。如果从空间使用效率考虑，可以使用head代替以上的node，含义一样，node比较好理解点。</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">与上题不同的是，由于此题引入了新的节点</span><span style="-en-paragraph: true;">dummy</span><span style="-en-paragraph: true;">，不可再使用</span><span style="-en-paragraph: true;">node-&gt;val == node-&gt;next-&gt;val</span><span style="-en-paragraph: true;">，原因有二：</span></div><ol><li>此题需要将值相等的节点全部删掉，而删除链表的操作与节点前后两个节点都有关系，故需要涉及三个链表节点。且删除单向链表节点时不能删除当前节点，只能改变当前节点的next指向的节点。</li><li>在判断val是否相等时需先确定node-&gt;next和node-&gt;next-&gt;next均不为空，否则不可对其进行取值。</li></ol></div><div><br/></div><div><h1>Partition List</h1></div><div><br/></div><h1>Add Two Numbers</h1><h4>Example</h4><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given</span> <span style="-en-paragraph: true;">7-&gt;1-&gt;6 + 5-&gt;9-&gt;2</span><span style="-en-paragraph: true;">. That is,</span> <span style="-en-paragraph: true;">617 + 295</span><span style="-en-paragraph: true;">.</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Return</span> <span style="-en-paragraph: true;">2-&gt;1-&gt;9</span><span style="-en-paragraph: true;">. That is</span> <span style="-en-paragraph: true;">912</span><span style="-en-paragraph: true;">.</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">Given</span> <span style="-en-paragraph: true;">3-&gt;1-&gt;5</span> <span style="-en-paragraph: true;">and</span> <span style="-en-paragraph: true;">5-&gt;9-&gt;2</span><span style="-en-paragraph: true;">, return</span> <span style="-en-paragraph: true;">8-&gt;0-&gt;8</span><span style="-en-paragraph: true;">.</span></div><h2>题解</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">一道看似简单的进位加法题，实则杀机重重，不信你不看答案自己先做做看。</span></div><div>首先由十进制加法可知应该注意进位的处理，但是这道题仅注意到这点就够了吗？还不够！因为两个链表长度有可能不等长！因此这道题的<b><font style="color: rgb(173, 0, 0);">亮点在于边界和异常条件的处理</font></b>，感谢 @wen 引入的 dummy 节点，处理起来更为优雅！</div><div><br/></div><div><h3>Python</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div># Definition for singly-linked list.</div><div># class ListNode(object):</div><div>#     def __init__(self, x):</div><div>#         self.val = x</div><div>#         self.next = None</div><div><br/></div><div>class Solution:</div><div>    def add_two_numbers(self, l1, l2):</div><div>        '''</div><div>        :type l1: ListNode</div><div>        :type l2: ListNode</div><div>        :rtype: ListNode</div><div>        '''</div><div>        carry = 0</div><div>        dummy = prev = ListNode(-1)</div><div>        while l1 or l2 or carry:</div><div>            v1 = l1.val if l1 else 0</div><div>            v2 = l2.val if l2 else 0</div><div>            val = (v1 + v2 + carry) % 10</div><div>            carry = (v1 + v2 + carry) / 10</div><div><br/></div><div>            prev.next = ListNode(val)</div><div>            prev = prev.next</div><div><br/></div><div>            if l1:</div><div>                l1 = l1.next</div><div>            if l2:</div><div>                l2 = l2.next</div><div>        return dummy.next</div></div></div><div><br/></div><div><h1>Two Lists Sum Advanced</h1></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>Given two numbers represented by two linked lists, write a function that returns sum list.</div><div>The sum list is linked list representation of addition of two input numbers.</div><div><br/></div><div>Example</div><div><br/></div><div>Input:</div><div>  First  List: 5-&gt;6-&gt;3  // represents number 563</div><div>  Second List: 8-&gt;4-&gt;2  // represents number 842</div><div>Output</div><div>  Resultant list: 1-&gt;4-&gt;0-&gt;5  // represents number 1405</div><div><br/></div><div>Challenge</div><div><br/></div><div>Not allowed to modify the lists.</div><div>Not allowed to use explicit extra space.</div></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div></div><div><br/></div></span>
</div></body></html> 